SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Threaded code</title>

</head>

Threaded code

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">Not to be confused with <a href="Multi-threaded_programming" class="mw-redirect" title="Multi-threaded programming">Multi-threaded programming</a> or <a href="Jump_threading" title="Jump threading">Jump threading</a>.</div>

In <a href="Computer_science" title="Computer science">computer science</a>, threaded code is a programming technique where the <a href="Source_code" title="Source code">code</a> has a form that essentially consists entirely of calls to <a href="Subroutine" class="mw-redirect" title="Subroutine">subroutines</a>. It is often used in <a href="Compiler" title="Compiler">compilers</a>, which may generate code in that form or be implemented in that form themselves. The code may be processed by an <a href="Interpreter_(computing)" title="Interpreter (computing)">interpreter</a> or it may simply be a sequence of <a href="Machine_code" title="Machine code">machine code</a> call instructions.

Threaded code has better <a href="Code_density" class="mw-redirect" title="Code density">density</a> than code generated by alternative generation techniques and by alternative <a href="Calling_convention" title="Calling convention">calling conventions</a>. In <a href="Cache_(computing)" title="Cache (computing)">cached</a> architectures, it may <a href="Execution_(computing)" title="Execution (computing)">execute</a> slightly slower. However, a program that is small enough to fit in a <a href="Computer_processor" class="mw-redirect" title="Computer processor">computer processor</a>'s <a href="CPU_cache" title="CPU cache">cache</a> may run faster than a larger program that suffers many <a href="Cache_miss" class="mw-redirect" title="Cache miss">cache misses</a>.<a href="#cite_note-tuwien1-1">[1]</a> Small programs may also be faster at <a href="Thread_switch" class="mw-redirect" title="Thread switch">thread switching</a>, when other programs have filled the cache.

Threaded code is best known for its use in many compilers of <a href="Programming_language" title="Programming language">programming languages</a>, such as <a href="Forth_(programming_language)" title="Forth (programming language)">Forth</a>, many implementations of <a href="BASIC" title="BASIC">BASIC</a>, some implementations of <a href="COBOL" title="COBOL">COBOL</a>, early versions of <a href="B_(programming_language)" title="B (programming language)">B</a>,<a href="#cite_note-2">[2]</a> and other languages for small <a href="Minicomputer" title="Minicomputer">minicomputers</a> and for <a href="Amateur_radio_satellite" title="Amateur radio satellite">amateur radio satellites</a>.

<div class="mw-heading mw-heading2"><h2 id="History">History</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

The common way to make computer programs is to use a <a href="Compiler" title="Compiler">compiler</a> to translate <a href="Source_code" title="Source code">source code</a> (written in some <a href="Symbolic_language_(programming)" title="Symbolic language (programming)">symbolic language</a>) to <a href="Machine_code" title="Machine code">machine code</a>. The resulting <a href="Executable" title="Executable">executable</a> is typically fast but, because it is specific to a <a href="Computer_hardware" title="Computer hardware">hardware</a> platform, it isn't portable. A different approach is to generate <a href="Instruction_set" class="mw-redirect" title="Instruction set">instructions</a> for a <a href="Virtual_machine" title="Virtual machine">virtual machine</a> and to use an <a href="Interpreter_(computing)" title="Interpreter (computing)">interpreter</a> on each hardware platform. The interpreter instantiates the virtual machine environment and executes the instructions. Thus the interpreter, compiled to machine code, provides an abstraction layer for "interpreted languages" that only need little compilation to conform to that layer (compilation may be confined to generating an <a href="Abstract_Syntax_Tree" class="mw-redirect" title="Abstract Syntax Tree">Abstract Syntax Tree</a>) or even need no compilation at all (if the layer is designed to consume raw source code.)

Early computers had relatively little memory. For example, most <a href="Data_General_Nova" title="Data General Nova">Data General Nova</a>, <a href="IBM_1130" title="IBM 1130">IBM 1130</a>, and many of the first <a href="Microcomputer" title="Microcomputer">microcomputers</a> had only 4 kB of RAM installed. Consequently, a lot of time was spent trying to find ways to reduce a program's size, to fit in the available memory.

One solution is to use an interpreter which reads the symbolic language a bit at a time, and calls functions to perform the actions. As the source code is typically much <a href="Code_density" class="mw-redirect" title="Code density">denser</a> than the resulting machine code, this can reduce overall memory use. This was the reason <a href="Microsoft_BASIC" title="Microsoft BASIC">Microsoft BASIC</a> is an interpreter:<a href="#cite_note-3">[a]</a> its own code had to share the 4 kB memory of machines like the <a href="Altair_8800" title="Altair 8800">Altair 8800</a> with the user's source code. A compiler translates from a source language to machine code, so the compiler, source, and output must all be in memory at the same time. In an interpreter, there is no output.

Threaded code is a formatting style for compiled code that minimizes memory use. Instead of writing out every step of an operation at its every occurrence in the program, as was common in <a href="Macro_assembler" class="mw-redirect" title="Macro assembler">macro assemblers</a> for instance, the compiler writes each common bit of code into a subroutine. Thus, each bit exists in only one place in memory (see "<a href="Don't_repeat_yourself" title="Don't repeat yourself">Don't repeat yourself</a>"). The top-level application in these programs may consist of nothing but subroutine calls. Many of these subroutines, in turn, also consist of nothing but lower-level subroutine calls.

Mainframes and some early microprocessors such as the <a href="RCA_1802" title="RCA 1802">RCA 1802</a> required several instructions to call a subroutine. In the top-level application and in many subroutines, that sequence is constantly repeated, with only the subroutine address changing from one call to the next. This means that a program consisting of many function calls may have considerable amounts of repeated code as well.

To address this, threaded code systems used pseudo-code to represent function calls in a single operator. At run time, a tiny "interpreter" would scan over the top-level code, extract the subroutine's address in memory, and call it. In other systems, this same basic concept is implemented as a <a href="Branch_table" title="Branch table">branch table</a>, <a href="Dispatch_table" title="Dispatch table">dispatch table</a>, or <a href="Virtual_method_table" title="Virtual method table">virtual method table</a>, all of which consist of a table of subroutine addresses.

During the 1970s, hardware designers spent considerable effort to make subroutine calls faster and simpler. On the improved designs, only a single instruction is expended to call a subroutine, so the use of a pseudo-instruction saves no room. Additionally, the performance of these calls is almost free of additional overhead. Today, though almost all programming languages focus on isolating code into subroutines, they do so for code clarity and maintainability, not to save space.

Threaded code systems save room by replacing that list of function calls, where only the subroutine address changes from one call to the next, with a list of execution tokens, which are essentially function calls with the call opcode(s) stripped off, leaving behind only a list of addresses.<a href="#cite_note-4">[3]</a><a href="#cite_note-heller-5">[4]</a><a href="#cite_note-6">[5]</a><a href="#cite_note-7">[6]</a><a href="#cite_note-8">[7]</a>

Over the years, programmers have created many variations on that "interpreter" or "small selector". The particular address in the list of addresses may be extracted using an index, <a href="General-purpose_register" class="mw-redirect" title="General-purpose register">general-purpose register</a> or <a href="Pointer_(computer_programming)" title="Pointer (computer programming)">pointer</a>. The addresses may be direct or indirect, contiguous or non-contiguous (linked by pointers), relative or absolute, resolved at compile time or dynamically built. No single variation is "best" for all situations.

<div class="mw-heading mw-heading2"><h2 id="Development">Development</h2></div>

To save space, programmers squeezed the lists of subroutine calls into simple lists of subroutine addresses, and used a small loop to call each subroutine in turn. For example, the following pseudocode uses this technique to add two numbers A and B. In the example, the list is labeled thread and a variable ip (Instruction Pointer) tracks our place within the list. Another variable sp (Stack Pointer) contains an address elsewhere in memory that is available to hold a value temporarily.

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre>start:

ip = &thread // points to the address '&pushA', not the textual label 'thread'

top:

jump *ip++ // follow ip to address in thread, follow that address to subroutine, advance ip

thread:

&pushA

&pushB

&add

...

pushA:

jump top

pushB:

*sp++ = B

jump top

add:

addend1 = *--sp // Pop the top value off the stack

addend2 = *--sp // Pop second value off the stack

*sp++ = addend1 + addend2 // Add the two values together and store the result on the top of the stack

jump top

</pre></div>

The calling loop at <code>top</code> is so simple that it can be repeated inline at the end of each subroutine. Control now jumps once, from the end of a subroutine to the start of another, instead of jumping twice via <code>top</code>. For example:

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre>start:

ip = &thread // ip points to &pushA (which points to the first instruction of pushA)

jump *ip++ // send control to first instruction of pushA and advance ip to &pushB

thread:

&pushA

&pushB

&add

...

pushA:

jump *ip++ // send control where ip says to (i.e. to pushB) and advance ip

pushB:

*sp++ = B

jump *ip++

add:

jump *ip++

</pre></div>

This is called direct threaded code (DTC). Although the technique is older, the first widely circulated use of the term "threaded code" is probably James R. Bell's 1973 article "Threaded Code".<a href="#cite_note-9">[8]</a>

In 1970, <a href="Charles_H._Moore" title="Charles H. Moore">Charles H. Moore</a> invented a more compact arrangement, indirect threaded code (ITC), for his Forth virtual machine. Moore arrived at this arrangement because <a href="Data_General_Nova" title="Data General Nova">Nova</a> minicomputers had an <a href="Indirection_bit" class="mw-redirect" title="Indirection bit">indirection bit</a> in every address, which made ITC easy and fast. Later, he said that he found it so convenient that he propagated it into all later Forth designs.<a href="#cite_note-10">[9]</a>

Today, some Forth compilers generate direct-threaded code while others generate indirect-threaded code. The executables act the same either way.

<div class="mw-heading mw-heading2"><h2 id="Threading_models">Threading models</h2></div>

Practically all executable threaded code uses one or another of these methods for invoking subroutines (each method is called a "threading model").

<div class="mw-heading mw-heading3"><h3 id="Direct_threading">Direct threading</h3></div>

Addresses in the thread are the addresses of machine language. This form is simple, but may have overheads because the thread consists only of machine addresses, so all further parameters must be loaded indirectly from memory. Some Forth systems produce direct-threaded code. On many machines direct-threading is faster than subroutine threading (see reference below).

An example of a <a href="Stack_machine" title="Stack machine">stack machine</a> might execute the sequence "push A, push B, add". That might be translated to the following thread and routines, where <code>ip</code> is initialized to the address labeled <code>thread</code> (i.e., the address where <code>&pushA</code> is stored).

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre>#define PUSH(x) (*sp++ = (x))

#define POP() (*--sp)

start:

ip = &thread // ip points to &pushA (which points to the first instruction of pushA)

jump *ip++ // send control to first instruction of pushA and advance ip to &pushB

thread:

&pushA

&pushB

&add

...

pushA:

PUSH(A)

jump *ip++ // send control where ip says to (i.e. to pushB) and advance ip

pushB:

PUSH(B)

jump *ip++

add:

result = POP() + POP()

PUSH(result)

jump *ip++

</pre></div>

Alternatively, operands may be included in the thread. This can remove some indirection needed above, but makes the thread larger:

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre>#define PUSH(x) (*sp++ = (x))

#define POP() (*--sp)

start:

ip = &thread

jump *ip++

thread:

&push

&A // address where A is stored, not literal A

&push

&B

&add

...

push:

variable_address = *ip++ // must move ip past operand address, since it is not a subroutine address

PUSH(*variable_address) // Read value from variable and push on stack

jump *ip++

add:

PUSH(result)

jump *ip++

</pre></div>

<div class="mw-heading mw-heading3"><h3 id="Indirect_threading">Indirect threading</h3></div>

Indirect threading uses pointers to locations that in turn point to machine code. The indirect pointer may be followed by operands which are stored in the indirect "block" rather than storing them repeatedly in the thread. Thus, indirect code is often more compact than direct-threaded code. The indirection typically makes it slower, though usually still faster than bytecode interpreters. Where the handler operands include both values and types, the space savings over direct-threaded code may be significant. Older FORTH systems typically produce indirect-threaded code.

For example, if the goal is to execute "push A, push B, add", the following might be used. Here, <code>ip</code> is initialized to address <code>&thread</code>, each code fragment (<code>push</code>, <code>add</code>) is found by double-indirecting through <code>ip</code> and an indirect block; and any operands to the fragment are found in the indirect block following the fragment's address. This requires keeping the current subroutine in <code>ip</code>, unlike all previous examples where it contained the next subroutine to be called.

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre>start:

jump *(*ip) // follow pointers to 1st instruction of 'push', DO NOT advance ip yet

thread:

&i_pushA

&i_pushB

&i_add

...

i_pushA:

&push

&A

i_pushB:

&push

&B

i_add:

&add

push:

*sp++ = *(*ip + 1) // look 1 past start of indirect block for operand address

jump *(*++ip) // advance ip in thread, jump through next indirect block to next subroutine

add:

addend1 = *--sp

addend2 = *--sp

jump *(*++ip)

</pre></div>

<div class="mw-heading mw-heading3"><h3 id="Subroutine_threading">Subroutine threading</h3></div>

So-called "subroutine-threaded code" (also "call-threaded code") consists of a series of machine-language "call" instructions (or addresses of functions to "call", as opposed to direct threading's use of "jump"). Early compilers for <a href="ALGOL" title="ALGOL">ALGOL</a>, Fortran, Cobol and some Forth systems often produced subroutine-threaded code. The code in many of these systems operated on a last-in-first-out (LIFO) stack of operands, for which compiler theory was well-developed. Most modern processors have special hardware support for subroutine "call" and "return" instructions, so the overhead of one extra machine instruction per dispatch is somewhat diminished.

Anton Ertl, the <a href="Gforth" title="Gforth">Gforth</a> compiler's co-creator, stated that "in contrast to popular myths, subroutine threading is usually slower than direct threading".<a href="#cite_note-11">[10]</a> However, Ertl's most recent tests<a href="#cite_note-tuwien1-1">[1]</a> show that subroutine threading is faster than direct threading in 15 out of 25 test cases. More specifically, he found that direct threading is the fastest threading model on Xeon, Opteron, and Athlon processors, indirect threading is fastest on Pentium M processors, and subroutine threading is fastest on Pentium 4, Pentium III, and PPC processors.

As an example of call threading for "push A, push B, add":

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre>thread:

call pushA

call pushB

call add

ret

pushA:

*sp++ = A

ret

pushB:

*sp++ = B

ret

add:

addend1 = *--sp

addend2 = *--sp

ret

</pre></div>

<div class="mw-heading mw-heading3"><h3 id="Token_threading">Token threading</h3></div>

Token-threaded code implements the thread as a list of indices into a table of operations; the index width is naturally chosen to be as small as possible for density and efficiency. 1 byte / 8-bits is the natural choice for ease of programming, but smaller sizes like 4-bits, or larger like 12 or 16 bits, can be used depending on the number of operations supported. As long as the index width is chosen to be narrower than a machine pointer, it will naturally be more compact than the other threading types without much special effort by the programmer. It is usually half to three-fourths the size of other threadings, which are themselves a quarter to an eighth the size of non-threaded code. The table's pointers can either be indirect or direct. Some Forth compilers produce token-threaded code. Some programmers consider the "<a href="P-code_machine" title="P-code machine">p-code</a>" generated by some <a href="Pascal_(programming_language)" title="Pascal (programming language)">Pascal</a> compilers, as well as the <a href="Bytecode" title="Bytecode">bytecodes</a> used by <a href=".NET_Framework" title=".NET Framework">.NET</a>, <a href="Java_(programming_language)" title="Java (programming language)">Java</a>, BASIC and some <a href="C_(programming_language)" title="C (programming language)">C</a> compilers, to be token-threading.

A common approach, historically, is <a href="Bytecode" title="Bytecode">bytecode</a>, which typically uses 8-bit opcodes with a stack-based virtual machine. The archetypal bytecode <a href="Interpreter_(computing)" title="Interpreter (computing)">interpreter</a> is known as a "decode and dispatch interpreter" and follows the form:

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre>start:

vpc = &thread

dispatch:

addr = decode(&vpc) // Convert the next bytecode operation to a pointer to machine code that implements it

// Any inter-instruction operations are performed here (e.g. updating global state, event processing, etc)

jump addr

CODE_PTR decode(BYTE_CODE **p) {

// In a more complex encoding, there may be multiple tables to choose between or control/mode flags

return table[*(*p)++];

}

thread: /* Contains bytecode, not machine addresses. Hence it is more compact. */

1 /*pushA*/

2 /*pushB*/

0 /*add*/

table:

&add /* table[0] = address of machine code that implements bytecode 0 */

&pushA /* table[1] ... */

&pushB /* table[2] ... */

pushA:

*sp++ = A

jump dispatch

pushB:

*sp++ = B

jump dispatch

add:

addend1 = *--sp

addend2 = *--sp

jump dispatch

</pre></div>

If the virtual machine uses only byte-size instructions, <code>decode()</code> is simply a fetch from <code>thread</code>, but often there are commonly used 1-byte instructions plus some less-common multibyte instructions (see <a href="Complex_instruction_set_computer" title="Complex instruction set computer">complex instruction set computer</a>), in which case <code>decode()</code> is more complex. The decoding of single byte opcodes can be very simply and efficiently handled by a branch table using the opcode directly as an index.

For instructions where the individual operations are simple, such as "push" and "add", the <a href="Computational_overhead" class="mw-redirect" title="Computational overhead">overhead</a> involved in deciding what to execute is larger than the cost of actually executing it, so such interpreters are often much slower than machine code. However, for more complex ("compound") instructions, the overhead percentage is proportionally less significant.

There are times when token-threaded code can sometimes run faster than the equivalent machine code when that machine code ends up being too large to fit in the physical CPU's L1 instruction cache. The higher <a href="Code_density" class="mw-redirect" title="Code density">code density</a> of threaded code, especially token-threaded code, can allow it to fit entirely in the L1 cache when it otherwise would not have, thereby avoiding cache thrashing. However, threaded code consumes both instruction cache (for the implementation of each operation) as well as data cache (for the bytecode and tables) unlike machine code which only consumes instruction cache; this means threaded code will eat into the budget for the amount of data that can be held for processing by the CPU at any given time. In any case, if the problem being computed involves applying a large number of operations to a small amount of data then using threaded code may be an ideal optimization.

<div class="mw-heading mw-heading3"><h3 id="Huffman_threading">Huffman threading</h3></div>

Huffman threaded code consists of lists of tokens stored as <a href="Huffman_code" class="mw-redirect" title="Huffman code">Huffman codes</a>. A Huffman code is a variable-length string of bits that identifies a unique token. A Huffman-threaded interpreter locates subroutines using an index table or a tree of pointers that can be navigated by the Huffman code. Huffman-threaded code is one of the most compact representations known for a computer program. The index and codes are chosen by measuring the frequency of calls to each subroutine in the code. Frequent calls are given the shortest codes. Operations with approximately equal frequencies are given codes with nearly equal bit-lengths. Most Huffman-threaded systems have been implemented as direct-threaded Forth systems, and used to pack large amounts of slow-running code into small, cheap <a href="Microcontroller" title="Microcontroller">microcontrollers</a>. Most published<a href="#cite_note-huffman-12">[11]</a> uses have been in smart cards, toys, calculators, and watches. The bit-oriented tokenized code used in <a href="PBASIC" title="PBASIC">PBASIC</a> can be seen as a kind of Huffman-threaded code.

<div class="mw-heading mw-heading3"><h3 id="Lesser-used_threading">Lesser-used threading</h3></div>

An example is string threading, in which operations are identified by strings, usually looked up by a hash table. This was used in Charles H. Moore's earliest Forth implementations and in the <a href="University_of_Illinois_at_Urbana%E2%80%93Champaign" class="mw-redirect" title="University of Illinois at Urbana–Champaign">University of Illinois</a>'s experimental hardware-interpreted computer language. It is also used in Bashforth.

<a href="Hewlett-Packard" title="Hewlett-Packard">HP</a>'s <a href="RPL_(programming_language)" title="RPL (programming language)">RPL</a>, first introduced in the <a href="HP-18C" title="HP-18C">HP-18C</a> calculator in 1986, is a type of proprietary hybrid (direct-threaded and indirect-threaded) threaded interpretive language (TIL)<a href="#cite_note-Loelinger_1981-13">[12]</a> that, unlike other TILs, allows embedding of RPL "objects" into the "runstream", i.e. the stream of addresses through which the interpreter pointer advances. An RPL "object" can be thought of as a special data type whose in-memory structure contains an address to an "object prolog" at the start of the object, and then data or executable code follows. The object prolog determines how the object's body should be executed or processed. Using the "RPL inner loop",<a href="#cite_note-Busby_2018-14">[13]</a> which was invented and patented<a href="#cite_note-Wickes_1986-15">[14]</a> by William C. Wickes in 1986 and published in 1988, execution follows like so:<a href="#cite_note-Wickes_1988-16">[15]</a>

<ol><li>Dereference the IP (instruction pointer) and store it into O (current object pointer)</li>

<li>Increment the IP by the length of one address pointer</li>

<li>Dereference O and store its address in O_1 (this is the second level of indirection)</li>

<li>Transfer control to next pointer or embedded object by setting the PC (program counter) to O_1 plus one address pointer</li>

This can be represented more precisely by:

<pre> O = [I]

I = I + Δ

PC = [O] + Δ

</pre>

Where above, O is the current object pointer, I is the interpreter pointer, Δ is the length of one address word and the "[]" operator stands for "dereference".

When control is transferred to an object pointer or an embedded object, execution continues as follows:

<pre>PROLOG -> PROLOG (The prolog address at the start of the prolog code points to itself)

IF O + Δ =/= PC

THEN GOTO INDIRECT (Test for direct execution)

O = I - Δ (Correct O to point to start of embedded object)

I = I + α (Correct I to point after embedded object where α is the length of the object)

INDIRECT (Rest of prolog)

</pre>

On HP's <a href="HP_Saturn" title="HP Saturn">Saturn</a> microprocessors that use RPL, there is a third level of indirection made possible by an architectural / programming trick which allows faster execution.<a href="#cite_note-Busby_2018-14">[13]</a>

<div class="mw-heading mw-heading2"><h2 id="Branches">Branches</h2></div>

In all interpreters, a branch simply changes the thread pointer (<code>ip</code>) to a different address in the thread. A conditional jump-if-zero branch that jumps only if the top-of-stack value is zero could be implemented as shown below. This example uses the embedded parameter version of direct threading so the <code>&thread[123]</code> line is the destination of where to jump if the condition is true, so it must be skipped (<code>ip++</code>) over if the branch is not taken.

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre>thread:

...

&brz

&thread[123]

...

brz:

when_true_ip = *ip++ // Get destination address for branch

if (*--sp == 0) // Pop/Consume top of stack and check if it's zero

ip = when_true_ip

jump *ip++

</pre></div>

<div class="mw-heading mw-heading2"><h2 id="Common_amenities">Common amenities</h2></div>

Separating the data and return stacks in a machine eliminates a great deal of stack management code, substantially reducing the size of the threaded code. The dual-stack principle originated three times independently: for <a href="Burroughs_large_systems" class="mw-redirect" title="Burroughs large systems">Burroughs large systems</a>, <a href="Forth_(programming_language)" title="Forth (programming language)">Forth</a>, and <a href="PostScript" title="PostScript">PostScript</a>. It is used in some <a href="Java_virtual_machine" title="Java virtual machine">Java virtual machines</a>.

Three <a href="Processor_register" title="Processor register">registers</a> are often present in a threaded virtual machine. Another one exists for passing data between <a href="Subroutine" class="mw-redirect" title="Subroutine">subroutines</a> ('words'). These are:

<ul><li>ip or i (<a href="Instruction_pointer" class="mw-redirect" title="Instruction pointer">instruction pointer</a>) of the virtual machine (not to be confused with the <a href="Program_counter" title="Program counter">program counter</a> of the underlying hardware implementing the VM)</li>

<li>w (work pointer)</li>

<li>rp or r (return <a href="Stack_(data_structure)" class="mw-redirect" title="Stack (data structure)">stack</a> pointer)</li>

<li>sp or s (<a href="Parameter" title="Parameter">parameter</a> stack pointer for passing parameters between words)</li></ul>

Often, threaded <a href="Virtual_machine" title="Virtual machine">virtual machines</a>, such as implementations of Forth, have a simple virtual machine at heart, consisting of three primitives. Those are:

<ol><li>nest, also called docol</li>

<li>unnest, or semi_s (;s)</li>

In an indirect-threaded virtual machine, the one given here, the operations are:

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre> next:

*ip++ -> w

jump **w++

nest:

ip -> *rp++

w -> ip

next

unnest:

*--rp -> ip

next

</pre></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .portalbox{padding:0;margin:0.5em 0;display:table;box-sizing:border-box;max-width:175px;list-style:none}.mw-parser-output .portalborder{border:1px solid var(--border-color-base,#a2a9b1);padding:0.1em;background:var(--background-color-neutral-subtle,#f8f9fa)}.mw-parser-output .portalbox-entry{display:table-row;font-size:85%;line-height:110%;height:1.9em;font-style:italic;font-weight:bold}.mw-parser-output .portalbox-image{display:table-cell;padding:0.2em;vertical-align:middle;text-align:center}.mw-parser-output .portalbox-link{display:table-cell;padding:0.2em 0.2em 0.2em 0.3em;vertical-align:middle}@media(min-width:720px){.mw-parser-output .portalleft{margin:0.5em 1em 0.5em 0}.mw-parser-output .portalright{clear:right;float:right;margin:0.5em 0 0.5em 1em}}

/* end https://en.wikipedia.org/ */

</style>

<ul><li><a href="Continuation-passing_style" title="Continuation-passing style">Continuation-passing style</a>, which replaces the global variable <code>ip</code> with a function parameter</li>

<li><a href="Just-in-time_compilation" title="Just-in-time compilation">Just-in-time compilation</a></li>

<li><a href="Return-oriented_programming" title="Return-oriented programming">Return-oriented programming</a>: the rediscovery of threaded code in order to exploit remote vulnerable systems.</li>

<li><a href="History_of_general-purpose_CPUs" title="History of general-purpose CPUs">History of general-purpose CPUs</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist reflist-lower-alpha">

<li id="cite_note-3"><a href="#cite_ref-3">^</a> <a href="Dartmouth_BASIC" title="Dartmouth BASIC">Dartmouth BASIC</a>, upon which <a href="Microsoft_BASIC" title="Microsoft BASIC">Microsoft BASIC</a> is ultimately based, was a compiler that ran on mainframe machines.

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://www.complang.tuwien.ac.at/forth/threading/">"Speed of various interpreter dispatch techniques V2"</a>.</cite>

</li>

<li id="cite_note-2"><a href="#cite_ref-2">^</a> Dennis M. Ritchie, <a rel="nofollow" class="external text" href="https://www.bell-labs.com/usr/dmr/www/chist.html">"The Development of the C Language"</a>, 1993. Quote: "The B compiler on the PDP-7 did not generate machine instructions, but instead 'threaded code' ..."

</li>

David Frech.

<a rel="nofollow" class="external text" href="https://muforth.nimblemachines.com/readme/">"muforth readme"</a>.

section "Simple and tail-recursive native compiler".

</li>

Steve Heller.

<a rel="nofollow" class="external text" href="https://books.google.com/books?id=gaajBQAAQBAJ">"Efficient C/C++ Programming: Smaller, Faster, Better"</a>.

2014.

Chapter 5: "Do you need an interpreter?"

p. 195.

</li>

Jean-Paul Tremblay; P. G. Sorenson.

<a rel="nofollow" class="external text" href="https://books.google.com/books?id=MacmAAAAMAAJ">"The Theory and Practice of Compiler Writing"</a>.

1985.

p. 527

</li>

<a rel="nofollow" class="external text" href="https://books.google.com/books?id=4WJVAAAAYAAJ">"Wireless World: Electronics, Radio, Television, Volume 89"</a>.

p. 73.

</li>

<a rel="nofollow" class="external text" href="https://books.google.com/books?id=ZWIfAAAAMAAJ">"Byte, Volume 5"</a>.

1980.

p. 212

</li>

<li id="cite_note-9"><a href="#cite_ref-9">^</a> <cite id="CITEREFBell1973" class="citation journal cs1">Bell, James R. (1973). <a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F362248.362270">"Threaded code"</a>. Communications of the ACM. 16 (6): 370–372. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F362248.362270">10.1145/362248.362270</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:19042952">19042952</a>.</cite>

</li>

<li id="cite_note-10"><a href="#cite_ref-10">^</a> Moore, Charles H., published remarks in Byte Magazine's Forth Issue

</li>

<li id="cite_note-11"><a href="#cite_ref-11">^</a> <cite id="CITEREFErtl" class="citation web cs1">Ertl, Anton. <a rel="nofollow" class="external text" href="http://www.complang.tuwien.ac.at/forth/threaded-code.html#what">"What is Threaded Code?"</a>.</cite>

</li>

<li id="cite_note-huffman-12"><a href="#cite_ref-huffman_12-0">^</a> <cite id="CITEREFLatendresseFeeley" class="citation book cs1">Latendresse, Mario; Feeley, Marc. Generation of Fast Interpreters for Huffman-Compressed Bytecode. Elsevier. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.156.2546">10.1.1.156.2546</a>.</cite>

</li>

<li id="cite_note-Loelinger_1981-13"><a href="#cite_ref-Loelinger_1981_13-0">^</a> <cite id="CITEREFLoelinger1981" class="citation book cs1 cs1-prop-location-test">Loelinger, R. G. (1981) [August 1979]. Written at Dayton, Ohio, USA. <a rel="nofollow" class="external text" href="https://archive.org/details/R.G.LoeligerThreadedInterpretiveLanguagesTheirDesignAndImplementationByteBooks1981">Threaded Interpretive Languages: Their Design and Implementation</a> (2nd printing, 1st ed.). Peterborough, New Hampshire, UK: <a href="BYTE_Books" class="mw-redirect" title="BYTE Books">BYTE Books</a>, <a href="BYTE_Publications_Inc." class="mw-redirect" title="BYTE Publications Inc.">BYTE Publications Inc.</a> <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-07038360-X</bdi>. <a href="LCCN_(identifier)" class="mw-redirect" title="LCCN (identifier)">LCCN</a> <a rel="nofollow" class="external text" href="https://lccn.loc.gov/80-19392">80-19392</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-07038360-9</bdi>. Retrieved 2023-08-03.</cite> (xiv+2+251 pages)

</li>

<li id="cite_note-Busby_2018-14">^ <a href="#cite_ref-Busby_2018_14-0">a</a> <a href="#cite_ref-Busby_2018_14-1">b</a> <cite id="CITEREFBusby2018" class="citation web cs1">Busby, Jonathan (2018-09-07). <a rel="nofollow" class="external text" href="https://www.hpmuseum.org/forum/thread-11358.html">"The RPL inner loop explained"</a>. The Museum of HP Calculators. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20230803201320/https://www.hpmuseum.org/forum/thread-11358.html">Archived</a> from the original on 2023-08-03. Retrieved 2019-12-27.</cite>

</li>

<li id="cite_note-Wickes_1986-15"><a href="#cite_ref-Wickes_1986_15-0">^</a> <cite id="CITEREFWickes1986" class="citation web cs1">Wickes, William C. (1986-05-30). <a rel="nofollow" class="external text" href="http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO2&Sect2=HITOFF&u=%2Fnetahtml%2FPTO%2Fsearch-adv.htm&r=8&p=1&f=G&l=50&d=PTXT&S1=((%22Hewlett+Packard%22.ASNM.)+AND+Wickes.INNM.)&OS=AN/%22Hewlett+Packard%22+and+IN/Wickes&RS=(AN/%22Hewlett+Packard%22+AND+IN/Wickes)">"Data processing system and method for the direct and indirect execution of uniformly structured object types"</a>. uspto.gov. Retrieved 2019-12-27.</cite>

</li>

<li id="cite_note-Wickes_1988-16"><a href="#cite_ref-Wickes_1988_16-0">^</a> <cite id="CITEREFWickes1988" class="citation conference cs1">Wickes, William C. (1988-10-01) [14–18 June 1988]. Forsely, Lawrence P. (ed.). <a rel="nofollow" class="external text" href="https://dl.acm.org/doi/abs/10.5555/534949">RPL: A Mathematical Control Language</a>. Proceedings of the 1988 Rochester Forth Conference: Programming Environments. Vol. 8. Rochester, New York, USA: Institute for Applied Forth Research, Inc., <a href="University_of_Rochester" title="University of Rochester">University of Rochester</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-91459308-9</bdi>. <a href="OCLC_(identifier)" class="mw-redirect" title="OCLC (identifier)">OCLC</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/oclc/839704944">839704944</a>.</cite> (NB. This title is often cited as "RPL: A Mathematics Control Language". An excerpt is available at: <a rel="nofollow" class="external text" href="https://web.archive.org/web/20230328115142/https://www.hpcalc.org/details/1743">RPLMan from Goodies Disk 4</a><a rel="nofollow" class="external text" href="https://web.archive.org/web/20220419184811/https://www.hpcalc.org/hp48/docs/programming/rplman.zip">Zip File</a>)

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="Further_reading">Further reading</h2></div>

<ul><li><a rel="nofollow" class="external text" href="http://cm.bell-labs.com/cm/cs/who/dmr/chist.html">The Development of the C Language</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20150328220551/http://cm.bell-labs.com/cm/cs/who/dmr/chist.html">Archived</a> 2015-03-28 at the <a href="Wayback_Machine" title="Wayback Machine">Wayback Machine</a> by <a href="Dennis_Ritchie" title="Dennis Ritchie">Dennis M. Ritchie</a> describes B (a precursor of C) as implemented using "threaded code".</li>

<li><cite id="CITEREFHorn" class="citation web cs1">Horn, Joseph K. <a rel="nofollow" class="external text" href="http://www.hpcalc.org/hp48/docs/programming/rpl3.txt">"What is RPL?"</a>. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20170917221524/http://www.hpcalc.org/hp48/docs/programming/rpl3.txt">Archived</a> from the original on 2017-09-17. Retrieved 2017-09-17.</cite> (NB. Brief overview on the threaded languages, System and User RPL, used on the HP calculators like the <a href="HP_48" class="mw-redirect" title="HP 48">HP 48</a>.)</li></ul>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li>Anton Ertl's explanatory page <a rel="nofollow" class="external text" href="http://www.complang.tuwien.ac.at/forth/threaded-code.html">What is Threaded Code?</a> describes different threading techniques and provides further references.</li>

<li><a rel="nofollow" class="external text" href="https://thinking-forth.sourceforge.net/">Thinking Forth Project</a> includes the seminal (but out of print) book Thinking Forth by <a rel="nofollow" class="external text" href="https://home.earthlink.net/~lbrodie/">Leo Brodie</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20051113041339/http://home.earthlink.net/~lbrodie/">Archived</a> 2005-11-13 at the <a href="Wayback_Machine" title="Wayback Machine">Wayback Machine</a> published in 1984.</li>

<li><a rel="nofollow" class="external text" href="http://www.forth.com/starting-forth/">Starting FORTH</a> online version of the book Starting FORTH by <a rel="nofollow" class="external text" href="https://home.earthlink.net/~lbrodie/">Leo Brodie</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20051113041339/http://home.earthlink.net/~lbrodie/">Archived</a> 2005-11-13 at the <a href="Wayback_Machine" title="Wayback Machine">Wayback Machine</a> published in 1981.</li>

<li>Brad Rodriguez's <a rel="nofollow" class="external text" href="http://www.bradrodriguez.com/papers/moving1.htm">Moving FORTH: Part 1: Design Decisions in the Forth Kernel</a> covers threading techniques in depth.</li>

<li><a rel="nofollow" class="external text" href="https://gcc.gnu.org/onlinedocs/gcc/Labels-as-Values.html">GCC extensions. Labels as Values</a></li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2024-12-04" href="https://en.wikipedia.org/wiki/?title=Threaded_code&oldid=1261173728">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>